/*!The Treasure Box Library
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 * 
 * Copyright (C) 2009 - 2017, TBOOX Open Source Group.
 *
 * @author      ruki
 * @file        idivi8.c
 * @ingroup     libm
 *
 */

/* //////////////////////////////////////////////////////////////////////////////////////
 * includes
 */
#include "math.h"

/* //////////////////////////////////////////////////////////////////////////////////////
 * implementation
 */
tb_uint32_t tb_idivi8(tb_uint32_t x, tb_uint8_t y)
{
    /* x * inverse[y] >> 32 == x / y for all 0 <= x <= 16909558 && 2 <= y <= 256 for x > 16909558
     * is an overestimate by less than 1 part in 1 << 24
     */
    static tb_uint32_t const inverse[257] = 
    {
            0,              4294967295U,    2147483648U,    1431655766,     1073741824,     858993460,      715827883,      613566757
    ,       536870912,      477218589,      429496730,      390451573,      357913942,      330382100,      306783379,      286331154
    ,       268435456,      252645136,      238609295,      226050911,      214748365,      204522253,      195225787,      186737709
    ,       178956971,      171798692,      165191050,      159072863,      153391690,      148102321,      143165577,      138547333
    ,       134217728,      130150525,      126322568,      122713352,      119304648,      116080198,      113025456,      110127367
    ,       107374183,      104755300,      102261127,      99882961,       97612894,       95443718,       93368855,       91382283
    ,       89478486,       87652394,       85899346,       84215046,       82595525,       81037119,       79536432,       78090315
    ,       76695845,       75350304,       74051161,       72796056,       71582789,       70409300,       69273667,       68174085
    ,       67108864,       66076420,       65075263,       64103990,       63161284,       62245903,       61356676,       60492498
    ,       59652324,       58835169,       58040099,       57266231,       56512728,       55778797,       55063684,       54366675
    ,       53687092,       53024288,       52377650,       51746594,       51130564,       50529028,       49941481,       49367441
    ,       48806447,       48258060,       47721859,       47197443,       46684428,       46182445,       45691142,       45210183
    ,       44739243,       44278014,       43826197,       43383509,       42949673,       42524429,       42107523,       41698712
    ,       41297763,       40904451,       40518560,       40139882,       39768216,       39403370,       39045158,       38693400
    ,       38347923,       38008561,       37675152,       37347542,       37025581,       36709123,       36398028,       36092163
    ,       35791395,       35495598,       35204650,       34918434,       34636834,       34359739,       34087043,       33818641
    ,       33554432,       33294321,       33038210,       32786010,       32537632,       32292988,       32051995,       31814573
    ,       31580642,       31350127,       31122952,       30899046,       30678338,       30460761,       30246249,       30034737
    ,       29826162,       29620465,       29417585,       29217465,       29020050,       28825284,       28633116,       28443493
    ,       28256364,       28071682,       27889399,       27709467,       27531842,       27356480,       27183338,       27012373
    ,       26843546,       26676816,       26512144,       26349493,       26188825,       26030105,       25873297,       25718368
    ,       25565282,       25414008,       25264514,       25116768,       24970741,       24826401,       24683721,       24542671
    ,       24403224,       24265352,       24129030,       23994231,       23860930,       23729102,       23598722,       23469767
    ,       23342214,       23216040,       23091223,       22967740,       22845571,       22724695,       22605092,       22486740
    ,       22369622,       22253717,       22139007,       22025474,       21913099,       21801865,       21691755,       21582751
    ,       21474837,       21367997,       21262215,       21157475,       21053762,       20951060,       20849356,       20748635
    ,       20648882,       20550083,       20452226,       20355296,       20259280,       20164166,       20069941,       19976593
    ,       19884108,       19792477,       19701685,       19611723,       19522579,       19434242,       19346700,       19259944
    ,       19173962,       19088744,       19004281,       18920561,       18837576,       18755316,       18673771,       18592933
    ,       18512791,       18433337,       18354562,       18276457,       18199014,       18122225,       18046082,       17970575
    ,       17895698,       17821442,       17747799,       17674763,       17602325,       17530479,       17459217,       17388532
    ,       17318417,       17248865,       17179870,       17111424,       17043522,       16976156,       16909321,       16843010
    ,       16777216
    };

    return ((tb_size_t)((((tb_uint64_t)x) * inverse[y]) >> 32));
}
